/**
 * [74] 搜索二维矩阵
 *
 * @format
 * @lc app=leetcode.cn id=74 lang=javascript
 */

// @lc code=start
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */

// 二分法 矩阵降维
// 通过矩阵降维映射为一维数组实现一次二分法，使代码量大大减少
var searchMatrix = function (matrix, target) {
    // 矩阵信息常数 M 行 N 列
    const [M, N] = [matrix.length, matrix[0].length]
    // 左指针 l， 右指针 r， 索引 i
    let [l, r, i] = [0, M * N - 1, Math.floor((M * N) / 2)]
    // 当前元素值 num （矩阵降维）， 循环次数 count （防止 false 时 i 左右横跳无限循环）
    let [num, count] = [matrix[Math.floor(i / N)][i % N], 0]
    // 初始判断（防止遗漏 [[1]]）
    if (target == num) return true
    while (l < r && count <= (M * N) / 2) {
        num = matrix[Math.floor(i / N)][i % N]
        if (target > num) {
            l = i
            i = Math.floor((l + r) / 2) + 1
        } else if (target < num) {
            r = i
            i = Math.floor((l + r) / 2)
        } else if (target == num) return true
        count++
    }
    return false
}
// debugger
// const matrix = [[1,3]]
// // [
// //     [1, 3, 5, 7],
// //     [10, 11, 16, 20],
// //     [23, 30, 34, 60]
// // ]
// const target = 1
// // 13
// console.log(searchMatrix(matrix, target))
// @lc code=end
